Symantec Visual Cafe for Java 2.5/symantec-visual-cafe-2.5-database-dev-edition.iso/Visual Cafe Pro v1.0/SOURCE.BIN/Matrix.java

Java Source | 1997-06-19 | 14.8 KB | 631 lines

package symantec.itools.awt;

// ===================================================================================
// = Revision History
// ===================================================================================

// Matrix
//        This class implements a sparse matrix of objects
//

// 03/20/97    RKM        Made the class public as per customer request
//                    Removed bogus debugging code
//                    Removed compaction of empty rows code
// 03/27/97    RKM        Made class final (this class is not made to be extended)
//                    Followed example of Vector, and added JavaDoc, throws, & synchronized
//                    Made final
//                    Tried to make some sense of protection on methods & members
// 03/28/97    RKM        Un-privitized members
// 05/02/97 RKM     Fixed removeRow - made it actually work
// 05/02/97 RKM     Fixed insertRow - one of the loops was not checking for null

/**
 * This class implements a sparse matrix of objects.
 * @version 1.0, Nov 26, 1996
 * @author    Symantec
 */

public final class Matrix
{
    //--------------------------------------------------
    // public constructors
    //--------------------------------------------------

    /**
     * Constructs an empty matrix.
     */
    public Matrix()
    {
        rowHead = this;
    }

    //--------------------------------------------------
    // private constructors
    //--------------------------------------------------

    private Matrix(int r, int c, Object obj)
    {
        this(r, c, obj, null);
    }

    private Matrix(int r, int c, Object obj, Matrix rh, Matrix nr, Matrix ne)
    {
        if (rh == null)
        {
            if (c != 0)
            {
                rowHead = new Matrix(r, 0, null, null, nr, this);
            }
            else
            {
                rowHead = this;
            }
        }
        else
        {
            rowHead = rh;
        }

        row = r;
        col = c;
        o = obj;
        nextRow = nr;
        nextElt = ne;
    }

    private Matrix(int r, int c, Object obj, Matrix nr, Matrix ne)
    {
        this(r, c, obj, null, nr, ne);
    }

    private Matrix(int r, int c, Object obj, Matrix nr)
    {
        this(r, c, obj, null, nr, null);
    }

    //--------------------------------------------------
    // public methods
    //--------------------------------------------------

    /**
     * Adds the specified object as the last element of the vector.
     * @param r the row of the element to be added
     * @param c the column of the element to added
     * @param o the element to be added
     * @exception IllegalArgumentException If the element is already allocated
     * @see #updateElement
     */
    public synchronized void addElement(int r, int c, Object o)
        throws IllegalArgumentException
    {
        //find the correct row
        Matrix m = nearest(r, c);

        if (m.row != r)
        {
            m.setNextRow(new Matrix(r, c, o, m.nextRow).rowHead);
            return;
        }

        //m must equal row
        if (c == m.col && c == 0)
        {
            if (m.o != null)
            {
                //exception - should call update
                throw new IllegalArgumentException("Element already in Matrix");
            }
            else
            {
                m.o = o;
                return;
            }
        }

        m.nextElt = new Matrix(r, c, o, m.rowHead, m.nextRow, m.nextElt);
    }

    /**
     * Adds or updates the element at the specified index as needed.
     * @param r the row of the element to be added
     * @param c the column of the element to added
     * @param o the element to be added
     * @see #addElement
     */
    public synchronized void updateElement(int r, int c, Object obj)
    {
        Matrix m = nearest(r, c);

        try
        {
            if (m == null)
            {
                //first element in matrix
                addElement(r, c, obj);
            }
            else if (m.row != r || m.col != c)
            {
                m.addElement(r, c, obj);
            }
            else
            {
                //must be the element
                m.o = obj;
            }
        }
        catch(IllegalArgumentException iae)
        {
            iae.printStackTrace();
        }
    }

    /**
     * Removes all elements of the matrix. The matrix becomes empty.
     */
    public synchronized void removeAllElements()
    {
        nextRow = null;
        nextElt = null;
        o = null;
    }

    /**
     * Returns the element at the specified index.
     * @param r the row of the element to remove
     * @param c the column of the element to remove
     * @return the element at [r,c]
     * @exception ArrayIndexOutOfBoundsException an invalid
     * row & column was given.
     */
    public synchronized Object elementAt(int r, int c)
        throws ArrayIndexOutOfBoundsException
    {
        Matrix m = nearest(r, c);

        if (m == null || m.row != r || m.col != c || m.o == null)
            throw new ArrayIndexOutOfBoundsException("Element row=" + r + " col=" + c + " is not in matrix");

        return m.o;
    }

    /**
     * Deletes the element at the specified index.
     * @param r the row of the element to remove
     * @param c the column of the element to remove
     * @exception ArrayIndexOutOfBoundsException the index was invalid.
     */
    public synchronized void removeElementAt(int r, int c)
        throws ArrayIndexOutOfBoundsException
    {
        Matrix m = nearest(r, c);

        if (m == null || m.row != r || m.col != c)
            throw new ArrayIndexOutOfBoundsException("Element row=" + r + " col=" + c + " is not in matrix");

        if (c == 0)
        {
            m.o = null;
            return;
        }

        Matrix prev = m = m.rowHead;

        while(m.col != c)
        {
            prev = m;
            m = m.nextElt;
        }

        prev.nextElt = m.nextElt;
    }

    /**
     * Deletes all elements on the specified row.
     * @param r the row of elements to remove
     * @see #insertRow
     * @see #removeElementAt
     */
    public synchronized void removeRow(int r)
    {
        //Removing zero is a special case, essentially we have to change this
        if (r == 0)
        {
            this.o            = null;
            this.nextElt    = null;
            if (this.nextRow != null)
            {
                //Remove new zero elem from the row list and assign its data into this
                Matrix newZeroElem = this.nextRow;
                this.nextRow    = newZeroElem.nextRow;
                this.nextElt    = newZeroElem.nextElt;
                this.row        = newZeroElem.row;
                this.col        = newZeroElem.col;
                this.o            = newZeroElem.o;

                //Hook up rowHeads of the elements in zero elem (since it's now this)
                {
                    Matrix elemMatrix = this.nextElt;
                    while (elemMatrix != null)
                    {
                        elemMatrix.rowHead = this;
                        elemMatrix = elemMatrix.nextElt;
                    }
                }

                //Decrement row of all matrixs
                Matrix stepMatrix = this;
                while (stepMatrix != null)
                {
                    stepMatrix.updateRowNum(stepMatrix.row - 1);
                    stepMatrix = stepMatrix.nextRow;
                }
            }
        }
        else
        {
            //Find the matrix that comes before the row, if it exists
            Matrix stepMatrix = this.nextRow;
            Matrix lastRow = this;
            while (stepMatrix != null && stepMatrix.row < r)
            {
                lastRow = stepMatrix;
                stepMatrix = stepMatrix.nextRow;
            }

            if (stepMatrix != null)
            {
                //We have an explicit row matrix
                if (stepMatrix.row == r)
                {
                    //Skip it in the chain
                    lastRow.nextRow = stepMatrix.nextRow;

                    //???RKM??? I thought I understood this class, until this was required
                    //???RKM??? This is chicken blood - I don't know why it's here !!!
                    stepMatrix.o = null;
                    stepMatrix.nextElt = null;

                    //Advance a row (number changing purposes)
                    stepMatrix = stepMatrix.nextRow;
                }

                //Change the row numbers of all the remaining rows
                while (stepMatrix != null)
                {
                    stepMatrix.updateRowNum(stepMatrix.row - 1);
                    stepMatrix = stepMatrix.nextRow;
                }
            }
        }

        /* RKM Was
        Matrix m = nearest(r, 0);

        if (m.row == r)
        {
            m = m.rowHead;
            m.o = null;
            m.nextElt = null;
        }
        */
    }

    /**
     * Inserts a new row by incrementing the row number of all elements with
     * row indexes >= given row number.
     * @param r the number of the row to insert
     * @see #removeRow
     */
    public synchronized void insertRow(int r)
    {
        Matrix m, n;

        if (r == 0)
        {
            //???RKM??? I don't see how this can work ???

            //want to insert into first row
            m = new Matrix();
            m.setNextRow(this);
        }
        else
        {
            m = nearest(r-1, 0);
            n = new Matrix(r, 0, null, m.nextRow);
            m.setNextRow(n);
            m = n;
        }

        if (m.nextRow.row == r)
        {
            //slip and increment row numbers
            m = m.nextRow;

            while(m != null)
            {
                m.updateRowNum(++r);
                m = m.nextRow;
                if (m != null && m.row != r) return;
            }
        }
    }

    /**
     * Sorts all rows in ascending order by comparing elements at the given
     * column number using the provided CompareFunc.
     * @param f compares two objects and determines which one is less than the other
     * @param c the column number of elements to compare
     */
    public synchronized void sort(CompareFunc f, int c)
    {
        boolean first = true;
        Matrix  m = this,
                n = null;

        while(m != null)
        {
            n = findLeast(f, m, c, first);

            if (n != null)
            {
                if (m.row == 0 && first)
                {
                    first = false;
                    swapRows(n);
                    m = this;
                    continue;
                 }
                 else
                 {
                    swapRows(m, n);
                 }
            }

            if (first)
            {
                first = false;
                continue;
            }

            m = m.nextRow;
        }
    }

    /**
     * Prints the specified row to System.out.
     * @param r the row to print
     */
    public synchronized void printRow(int r)
    {
        Matrix m = nearest(r, 0);

        if (m.row != r)
        {
            m = m.nextRow;
            if (m.row != r)
            {
                System.out.println("Row " + r + " is not in the matrix");
                return;
            }
        }

        System.out.println("-------- Printing row " + r + " ----------");
        while(m != null)
        {
            System.out.println("Row=" + m.row + "  Col=" + m.col + "  value=" + m.o);
            m = m.nextElt;
        }
    }

    /**
     * Returns the number of rows in the matrix.
     */
    public synchronized int rows()
    {
        Matrix m = this;

        while(m.nextRow != null)
        {
            m = m.nextRow;
        }

        return (m.nextElt == null && m.o == null ? m.row : m.row+1);
    }

    //only call on row head
    private synchronized void updateRowNum(int r)
    {
        Matrix m = this;

        while(m != null)
        {
            m.row = r;
            m = m.nextElt;
        }
    }

    /**
     * Returns an enumeration of the elements. Use the Enumeration methods on
     * the returned object to fetch the elements sequentially.
     */
    public synchronized MatrixEnumeration elements()
    {
        return new MatrixEnumeration(this);
    }

    /**
     * Returns a string representation of this component.
     * This is a standard Java AWT method which gets called to generate
     * a string that represents this component.
     *
     * @return a meaningful string about this object
     */
    public synchronized String toString()
    {
        return "Matrix: row=" + row + " col=" + col + " o=" + o;
    }

    //--------------------------------------------------
    // private members
    //--------------------------------------------------

    private synchronized Matrix nearest(int r, int c)
    {
        //find the correct row
        Matrix m = this;

        while (r > m.row)
        {
            if (m.nextRow != null && m.nextRow.row <= r)
            {
                //further down pike so keep climbing
                m = m.nextRow;
            }
            else
            {
                return m;
            }
        }

        //m must equal row
        while (m.nextElt != null && c >= m.nextElt.col)
        {
            //further down the line
            m = m.nextElt;
        }

        return m;
    }

    private synchronized void setRowHead()
    {
        Matrix m = nextElt;
        Matrix h = this;

        while (m != null)
        {
            m.rowHead = h;
            m = m.nextElt;
        }
    }

    private synchronized void setNextRow(Matrix nr)
    {
        Matrix m = this;

        while(m != null)
        {
            m.nextRow = nr;
            m = m.nextElt;
        }
    }

    //m1 & m2 preceed the two rows to be switched.
    private synchronized void swapRows(Matrix p1, Matrix p2)
    {
        Matrix t1 = p1.nextRow;
        Matrix t1NextRow = t1.nextRow;
        Matrix t2 = p2.nextRow;
        Matrix t2NextRow = t2.nextRow;

        p1.setNextRow(t2);
        p2.setNextRow(t1);

        if (p2 == t1)
        {
            t2.setNextRow(t1);
        }
        else
        {
            t2.setNextRow(t1NextRow);
        }

        t1.setNextRow(t2NextRow);
        int t1Row = t1.row;
        t1.updateRowNum(t2.row);
        t2.updateRowNum(t1Row);
    }

    //swap the current row (must be the first) with the row following m2
    private synchronized void swapRows(Matrix m2)
    {
        Matrix t2 = m2.nextRow;
        Matrix t1 = new Matrix(-1, t2.col, o, null, nextElt);
        m2.rowHead.setNextRow(t1);
        t1.setNextRow(t2.nextRow);
        t1.updateRowNum(t2.row);
        t1.setRowHead();

        //fixup root node (that is this)
        nextElt = t2.nextElt;
        o = t2.o;
        setNextRow(nextRow);  //this.nextRow never changed so can use for update
        updateRowNum(0);
        setRowHead();
    }

    private synchronized Matrix findLeast(CompareFunc f, Matrix m, int c, boolean first)
    {
        //m is row previous to one to be compared to when m.row != 0
        if (!first)
            m = m.nextRow;

        if(m == null || m.nextRow == null)
            return null;

        Matrix n = m.nextRow.rowHead;
        Matrix prevToN = m.rowHead;
        Matrix prevToLeast = null;

        m = m.nearest(m.row, c);

        while (n != null)
        {
            n = n.nearest(n.row, c);

            if (n.col != c)
            {
                //no item for column on next row so keep searching
                prevToN = n.rowHead;
                n = n.nextRow;
                continue;
            }
            else if (m.col != c)
            {
                //no item for first column so automatically sent down
                m = n;
                prevToLeast = prevToN;
                continue;
            }

            if (f.lessThan(n.o, m.o))
            {
                //n < m so put n in for least
                m = n;
                prevToLeast = prevToN;
            }

            prevToN = n.rowHead;
            n = n.nextRow;
        }

        return prevToLeast;
    }

    //--------------------------------------------------
    // private members
    //--------------------------------------------------

    Matrix        rowHead;
    Matrix        nextRow;
    Matrix        nextElt;
    int            row;
    int            col;
    Object        o;
}

interface CompareFunc
{
    public abstract boolean lessThan(Object o1, Object o2);
}